package com.example.leetcode.prcatice;

/**
 * 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
 *
 * <p>示例 1：
 *
 * <p>输入：n = 13 输出：6
 */
public class Test233 {
    /**
     * 题解：求得各个位数出现1的个数并且相加即可 ，可以将数字分为cur（当前位置） high(高位） low(低位），cur值不同，分为三种情况，分别为cur = 0，1， 2~9
     * 当 cur = 0
     * 2304 最近一个十位数含1的数字是 2219
     * 假设当前 cur = 0
     * 2      2      1     9
     *   high      cur     low
     *忽略 cur ，只看高低位  0010 ~ 2219 即可得 000 ~ 229，所以出现1的次数为 229 -0 +1 = 230， 计算公式就是 high * 10
     * 假设cur = 1;  以 2314 为例
     * 2      3       1       4
     *   high        cur      low
     * 忽略cur，0010 ~ 2314   即可 000 ~ 234 ，所以出现1的次数为 234 -0 + 1 = 235 ，计算公式为 high*1+low+1；
     * 假设 cur = 2~9 是 以 2324为例
     * 2324最近一个包含1的是 2319
     * 2        3        1        9
     *   high            cur      low
     *  忽略cur   0010 ~ 2319 得到 000 ~ 239 ， 所以出现1的次数为 239 - 0+ 1 =240 ，计算公式为 (high+1)*10;
     *
     *
     * 同理计算各个位数含有1的次数相加即可
     * @param n
     * @return
     */
    public int countDigitOne(int n) {
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}
